HyperLib 1997 Winter - Disc 1/HYPERLIB-1997-Winter-CD1.ISO.7z/HYPERLIB-1997-Winter-CD1.ISO/オンラインウェア/PRG/PL 2.0 SupplementDoc Folder.sit/PL 2.0 SupplementDoc Folder/Documentation/Chapter 15. Lists

Text File | 1995-03-27 | 46KB | 1,244 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

15. Lists

A cons, or dotted pair, is a compound data object having two components called
the car and cdr. Each component may be any Lisp object. A list is a chain of
conses linked by cdr fields; the chain is terminated by some atom (a non-cons
object). An ordinary list is terminated by nil, the empty list (also written
()). A list whose cdr chain is terminated by some non-nil atom is called a
dotted list.

The recommended predicate for testing for the end of a list is endp.

-------------------------------------------------------------------------------

   *  Conses
   *  Lists
   *  Alteration of List Structure
   *  Substitution of Expressions
   *  Using Lists as Sets
   *  Association Lists

-------------------------------------------------------------------------------

15.1. Conses

These are the basic operations on conses viewed as pairs rather than as the
constituents of a list.

[Function]
car list

This returns the car of list, which must be a cons or (); that is, list must
satisfy the predicate listp. By definition, the car of () is (). If the cons is
regarded as the first cons of a list, then car returns the first element of the
list. For example:

(car '(a b c)) => a

See first. The car of a cons may be altered by using rplaca or setf.

[Function]
cdr list

This returns the cdr of list, which must be a cons or (); that is, list must
satisfy the predicate listp. By definition, the cdr of () is (). If the cons is
regarded as the first cons of a list, then cdr returns the rest of the list,
which is a list with all elements but the first of the original list. For
example:

(cdr '(a b c)) => (b c)

See rest. The cdr of a cons may be altered by using rplacd or setf.

[Function]
caar list
cadr list
cdar list
cddr list
caaar list
caadr list
cadar list
caddr list
cdaar list
cdadr list
cddar list
cdddr list
caaaar list
caaadr list
caadar list
caaddr list
cadaar list
cadadr list
caddar list
cadddr list
cdaaar list
cdaadr list
cdadar list
cdaddr list
cddaar list
cddadr list
cdddar list
cddddr list

All of the compositions of up to four car and cdr operations are defined as
separate Common Lisp functions. The names of these functions begin with c and
end with r, and in between is a sequence of a and d letters corresponding to
the composition performed by the function. For example:

(cddadr x) is the same as (cdr (cdr (car (cdr x))))

If the argument is regarded as a list, then cadr returns the second element of
the list, caddr the third, and cadddr the fourth. If the first element of a
list is a list, then caar is the first element of the sublist, cdar is the rest
of that sublist, and cadar is the second element of the sublist, and so on.

As a matter of style, it is often preferable to define a function or macro to
access part of a complicated data structure, rather than to use a long car/cdr
string. For example, one might define a macro to extract the list of parameter
variables from a lambda-expression:

(defmacro lambda-vars (lambda-exp) `(cadr ,lambda-exp))

and then use lambda-vars for this purpose instead of cadr. See also defstruct,
which will automatically define new record data types and access functions for
instances of them.

Any of these functions may be used to specify a place for setf.

[Function]
cons x y

cons is the primitive function to create a new cons whose car is x and whose
cdr is y. For example:

(cons 'a 'b) => (a . b)
(cons 'a (cons 'b (cons 'c '()))) => (a b c)
(cons 'a '(b c d)) => (a b c d)

cons may be thought of as creating a cons, or as adding a new element to the
front of a list.

[Function]
tree-equal x y &key :test :test-not

This is a predicate that is true if x and y are isomorphic trees with identical
leaves, that is, if x and y are atoms that satisfy the test (by default eql),
or if they are both conses and their car's are tree-equal and their cdr's are
tree-equal. Thus tree-equal recursively compares conses (but not any other
objects that have components). See equal, which does recursively compare
certain other structured objects, such as strings.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------

15.2. Lists

The following functions perform various operations on lists.

[change_begin]
The list is one of the original Lisp data types. The very name ``Lisp'' is an
abbreviation for ``LISt Processing.''
[change_end]

[Function]
endp object

The predicate endp is the recommended way to test for the end of a list. It is
false of conses, true of nil, and an error for all other arguments.

-------------------------------------------------------------------------------
Implementation note: Implementations are encouraged to signal an error,
especially in the interpreter, for a non-list argument. The endp function is
defined so as to allow compiled code to perform simply an atom check or a null
check if speed is more important than safety.
-------------------------------------------------------------------------------

[Function]
list-length list

list-length returns, as an integer, the length of list. list-length differs
from length when the list is circular; length may fail to return, whereas
list-length will return nil. For example:

(list-length '()) => 0
(list-length '(a b c d)) => 4
(list-length '(a (b c) d)) => 3
(let ((x (list 'a b c)))
  (rplacd (last x) x)
  (list-length x)) => nil

list-length could be implemented as follows:

(defun list-length (x)
  (do ((n 0 (+ n 2))            ;Counter
       (fast x (cddr fast))     ;Fast pointer: leaps by 2
       (slow x (cdr slow)))     ;Slow pointer: leaps by 1
      (nil)
    ;; If fast pointer hits the end, return the count.
    (when (endp fast) (return n))
    (when (endp (cdr fast)) (return (+ n 1)))
    ;; If fast pointer eventually equals slow pointer,
    ;;  then we must be stuck in a circular list.
    ;; (A deeper property is the converse: if we are
    ;;  stuck in a circular list, then eventually the
    ;;  fast pointer will equal the slow pointer.
    ;;  That fact justifies this implementation.)
    (when (and (eq fast slow) (> n 0)) (return nil))))

See length, which will return the length of any sequence.

[Function]
nth n list

(nth n list) returns the nth element of list, where the car of the list is the
``zeroth'' element. The argument n must be a non-negative integer. If the
length of the list is not greater than n, then the result is (), that is, nil.
(This is consistent with the idea that the car and cdr of () are each ().) For
example:

(nth 0 '(foo bar gack)) => foo
(nth 1 '(foo bar gack)) => bar
(nth 3 '(foo bar gack)) => ()

-------------------------------------------------------------------------------
Compatibility note: This is not the same as the Interlisp function called nth,
which is similar to but not exactly the same as the Common Lisp function
nthcdr. This definition of nth is compatible with Lisp Machine Lisp and NIL
(New Implementation of Lisp). Also, some people have used macros and functions
called nth of their own in their old MacLisp programs, which may not work the
same way.
-------------------------------------------------------------------------------

nth may be used to specify a place to setf; when nth is used in this way, the
argument n must be less than the length of the list.

Note that the arguments to nth are reversed from the order used by most other
sequence selector functions such as elt.

[Function]
first list
second list
third list
fourth list
fifth list
sixth list
seventh list
eighth list
ninth list
tenth list

These functions are sometimes convenient for accessing particular elements of a
list. first is the same as car, second is the same as cadr, third is the same
as caddr, and so on. Note that the ordinal numbering used here is one-origin,
as opposed to the zero-origin numbering used by nth:

(fifth x) == (nth 4 x)

setf may be used with each of these functions to store into the indicated
position of a list.

[Function]
rest list

rest means the same as cdr but mnemonically complements first. setf may be used
with rest to replace the cdr of a list with a new value.

[Function]
nthcdr n list

(nthcdr n list) performs the cdr operation n times on list, and returns the
result. For example:

(nthcdr 0 '(a b c)) => (a b c)
(nthcdr 2 '(a b c)) => (c)
(nthcdr 4 '(a b c)) => ()

In other words, it returns the nth cdr of the list.

-------------------------------------------------------------------------------
Compatibility note: This is similar to the Interlisp function nth, except that
the Interlisp function is one-based instead of zero-based.
-------------------------------------------------------------------------------

(car (nthcdr n x)) == (nth n x)

[change_begin]
X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED)   to clarify that the
argument n must be a non-negative integer.
[change_end]

[old_change_begin]

[Function]
last list

last returns the last cons (not the last element!) of list. If list is (), it
returns (). For example:

(setq x '(a b c d))
(last x) => (d)
(rplacd (last x) '(e f))
x => '(a b c d e f)
(last '(a b c . d)) => (c . d)

[old_change_end]

[change_begin]
X3J13 voted in June 1988 (LAST-N)   to extend the last function to accept an
optional second argument. The effect is to make last complementary in operation
to butlast. The new description (with some additional examples) would be as
follows.

[Function]
last list &optional (n 1)

last returns the tail of the list consisting of the last n conses of list. The
list may be a dotted list. It is an error if the list is circular.

The argument n must be a non-negative integer. If n is zero, then the atom that
terminates the list is returned. If n is not less than the number of cons cells
making up the list, then the list itself is returned.

For example:

(setq x '(a b c d))
(last x) => (d)
(rplacd (last x) '(e f))
x => '(a b c d e f)
(last x 3) => (d e f)
(last '()) => ()
(last '(a b c . d)) => (c . d)
(last '(a b c . d) 0) => d
(last '(a b c . d) 2) => (b c . d)
(last '(a b c . d) 1729) => (a b c . d)

[change_end]

[Function]
list &rest args

list constructs and returns a list of its arguments. For example:

(list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)

(list) => ()
(list (list 'a 'b) (list 'c 'd 'e)) => ((a b) (c d e))

[Function]
list* arg &rest others

list* is like list except that the last cons of the constructed list is
``dotted.'' The last argument to list* is used as the cdr of the last cons
constructed; this need not be an atom. If it is not an atom, then the effect is
to add several new elements to the front of a list. For example:

(list* 'a 'b 'c 'd) => (a b c . d)

This is like

(cons 'a (cons 'b (cons 'c 'd)))

Also:

(list* 'a 'b 'c '(d e f)) => (a b c d e f)
(list* x) == x

[Function]
make-list size &key :initial-element

This creates and returns a list containing size elements, each of which is
initialized to the :initial-element argument (which defaults to nil). size
should be a non-negative integer. For example:

(make-list 5) => (nil nil nil nil nil)
(make-list 3 :initial-element 'rah) => (rah rah rah)

[Function]
append &rest lists

The arguments to append are lists. The result is a list that is the
concatenation of the arguments. The arguments are not destroyed. For example:

(append '(a b c) '(d e f) '() '(g)) => (a b c d e f g)

Note that append copies the top-level list structure of each of its arguments
except the last. The function concatenate can perform a similar operation, but
always copies all its arguments. See also nconc, which is like append but
destroys all arguments but the last.

The last argument actually need not be a list but may be any Lisp object, which
becomes the tail end of the constructed list. For example, (append '(a b c) 'd)
=> (a b c . d).

(append x '()) is an idiom once frequently used to copy the list x, but the
copy-list function is more appropriate to this task.

[Function]
copy-list list

This returns a list that is equal to list, but not eq. Only the top level of
list structure is copied; that is, copy-list copies in the cdr direction but
not in the car direction. If the list is ``dotted,'' that is, (cdr (last list))
is a non-nil atom, this will be true of the returned list also. See also
copy-seq and copy-tree.

[Function]
copy-alist list

copy-alist is for copying association lists. The top level of list structure of
list is copied, just as for copy-list. In addition, each element of list that
is a cons is replaced in the copy by a new cons with the same car and cdr.

[Function]
copy-tree object

copy-tree is for copying trees of conses. The argument object may be any Lisp
object. If it is not a cons, it is returned; otherwise the result is a new cons
of the results of calling copy-tree on the car and cdr of the argument. In
other words, all conses in the tree are copied recursively, stopping only when
non-conses are encountered. Circularities and the sharing of substructure are
not preserved.

-------------------------------------------------------------------------------
Compatibility note: This function is called copy in Interlisp.
-------------------------------------------------------------------------------

[Function]
revappend x y

(revappend x y) is exactly the same as (append (reverse x) y) except that it is
potentially more efficient. Both x and y should be lists. The argument x is
copied, not destroyed. Compare this with nreconc, which destroys its first
argument.

[Function]
nconc &rest lists

nconc takes lists as arguments. It returns a list that is the arguments
concatenated together. The arguments are changed rather than copied. (Compare
this with append, which copies arguments rather than destroying them.) For
example:

(setq x '(a b c))
(setq y '(d e f))
(nconc x y) => (a b c d e f)
x => (a b c d e f)

Note, in the example, that the value of x is now different, since its last cons
has been rplacd'd to the value of y. If one were then to evaluate (nconc x y)
again, it would yield a piece of ``circular'' list structure, whose printed
representation would be (a b c d e f d e f d e f ...), repeating forever; if
the *print-circle* switch were non-nil, it would be printed as (a b c . #1=(d e
f . #1#)).

[change_begin]
X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
permissible side effects of certain operations. The side-effect behavior of
nconc is specified by a recursive relationship outlined in the following table,
in which a call to nconc matching the earliest possible pattern on the left is
required to have side-effect behavior equivalent to the corresponding
expression on the right.

(nconc)                 nil     ;No side effects
(nconc nil . r)         (nconc . r)
(nconc x)               x
(nconc x y)             (let ((p x) (q y))
                          (rplacd (last p) q)
                          p)
(nconc x y . r)         (nconc (nconc x y) . r)

[change_end]

[Function]
nreconc x y

(nreconc x y) is exactly the same as (nconc (nreverse x) y) except that it is
potentially more efficient. Both x and y should be lists. The argument x is
destroyed. Compare this with revappend.

(setq planets '(jupiter mars earth venus mercury))
(setq more-planets '(saturn uranus pluto neptune))
(nreconc more-planets planets)
=> (neptune pluto uranus saturn jupiter mars earth venus mercury)
  and now the value of more-planets is not well defined

[change_begin]
X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
permissible side effects of certain operations; (nreconc x y) is permitted and
required to have side-effect behavior equivalent to that of (nconc (nreverse x)
y).
[change_end]

[Macro]
push item place

The form place should be the name of a generalized variable containing a list;
item may refer to any Lisp object. The item is consed onto the front of the
list, and the augmented list is stored back into place and returned. The form
place may be any form acceptable as a generalized variable to setf. If the list
held in place is viewed as a push-down stack, then push pushes an element onto
the top of the stack. For example:

(setq x '(a (b c) d))
(push 5 (cadr x)) => (5 b c)  and now x => (a (5 b c) d)

The effect of (push item place) is roughly equivalent to

(setf place (cons item place))

except that the latter would evaluate any subforms of place twice, while push
takes care to evaluate them only once. Moreover, for certain place forms push
may be significantly more efficient than the setf version.

[change_begin]
X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)   to clarify order of
evaluation (see section 7.2). Note that item is fully evaluated before any part
of place is evaluated.
[change_end]

[Macro]
pushnew item place &key :test :test-not :key

The form place should be the name of a generalized variable containing a list;
item may refer to any Lisp object. If the item is not already a member of the
list (as determined by comparisons using the :test predicate, which defaults to
eql), then the item is consed onto the front of the list, and the augmented
list is stored back into place and returned; otherwise the unaugmented list is
returned. The form place may be any form acceptable as a generalized variable
to setf. If the list held in place is viewed as a set, then pushnew adjoins an
element to the set; see adjoin.

The keyword arguments to pushnew follow the conventions for the generic
sequence functions. See chapter 14. In effect, these keywords are simply passed
on to the adjoin function.

pushnew returns the new contents of the place. For example:

(setq x '(a (b c) d))
(pushnew 5 (cadr x)) => (5 b c)   and now x => (a (5 b c) d)
(pushnew 'b (cadr x)) => (5 b c)  and x is unchanged

The effect of

(pushnew item place :test p)

is roughly equivalent to

(setf place (adjoin item place :test p))

except that the latter would evaluate any subforms of place twice, while
pushnew takes care to evaluate them only once. Moreover, for certain place
forms pushnew may be significantly more efficient than the setf version.

[change_begin]
X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)   to clarify order of
evaluation (see section 7.2). Note that item is fully evaluated before any part
of place is evaluated.
[change_end]

[Macro]
pop place

The form place should be the name of a generalized variable containing a list.
The result of pop is the car of the contents of place, and as a side effect the
cdr of the contents is stored back into place. The form place may be any form
acceptable as a generalized variable to setf. If the list held in place is
viewed as a push-down stack, then pop pops an element from the top of the stack
and returns it. For example:

(setq stack '(a b c))
(pop stack) => a  and now stack => (b c)

The effect of (pop place) is roughly equivalent to

(prog1 (car place) (setf place (cdr place)))

except that the latter would evaluate any subforms of place three times, while
pop takes care to evaluate them only once. Moreover, for certain place forms
pop may be significantly more efficient than the setf version.

[change_begin]
X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)   to clarify order of
evaluation (see section 7.2).
[change_end]

[Function]
butlast list &optional n

This creates and returns a list with the same elements as list, excepting the
last n elements. n defaults to 1. The argument is not destroyed. If the list
has fewer than n elements, then () is returned. For example:

(butlast '(a b c d)) => (a b c)
(butlast '((a b) (c d))) => ((a b))
(butlast '(a)) => ()
(butlast nil) => ()

The name is from the phrase ``all elements but the last.''

[Function]
nbutlast list &optional n

This is the destructive version of butlast; it changes the cdr of the cons n+1
from the end of the list to nil. n defaults to 1. If the list has fewer than n
elements, then nbutlast returns (), and the argument is not modified.
(Therefore one normally writes (setq a (nbutlast a)) rather than simply
(nbutlast a).) For example:

(setq foo '(a b c d))
(nbutlast foo) => (a b c)
foo => (a b c)
(nbutlast '(a)) => ()
(nbutlast 'nil) => ()

[Function]
ldiff list sublist

list should be a list, and sublist should be a sublist of list, that is, one of
the conses that make up list. ldiff (meaning ``list difference'') will return a
new (freshly consed) list, whose elements are those elements of list that
appear before sublist. If sublist is not a tail of list (and in particular if
sublist is nil), then a copy of the entire list is returned. The argument list
is not destroyed. For example:

(setq x '(a b c d e))
(setq y (cdddr x)) => (d e)
(ldiff x y) => (a b c)

but (ldiff '(a b c d) '(c d)) => (a b c d)

since the sublist was not eq to any part of the list.

-------------------------------------------------------------------------------

15.3. Alteration of List Structure

The functions rplaca and rplacd may be used to make alterations in already
existing list structure, that is, to change the car or cdr of an existing cons.
One may also use setf in conjunction with car and cdr.

The structure is not copied but is destructively altered; hence caution should
be exercised when using these functions, as strange side effects can occur if
portions of list structure become shared. The nconc, nreverse, nreconc, and
nbutlast functions, already described, have the same property, as do certain of
the generic sequence functions such as delete. However, they are normally not
used for this side effect; rather, the list-structure modification is purely
for efficiency, and compatible non-modifying functions are provided.

[Function]
rplaca x y

(rplaca x y) changes the car of x to y and returns (the modified) x. x must be
a cons, but y may be any Lisp object. For example:

(setq g '(a b c))
(rplaca (cdr g) 'd) => (d c)
Now g => (a d c)

[Function]
rplacd x y

(rplacd x y) changes the cdr of x to y and returns (the modified) x. x must be
a cons, but y may be any Lisp object. For example:

(setq x '(a b c))
(rplacd x 'd) => (a . d)
Now x => (a . d)

[change_begin]
The functions rplaca and rplacd go back to the earliest origins of Lisp, along
with car, cdr, and cons. Nowadays, however, they seem to be falling by the
wayside. More and more Common Lisp programmers use setf for nearly all
structure modifications: (rplaca x y) is rendered as (setf (car x) y) or
perhaps as (setf (first x) y). Even more likely is that a defstruct structure
or a CLOS class is used in place of a list, if the data structure is at all
complicated; in this case setf is used with a slot accessor.
[change_end]

-------------------------------------------------------------------------------

15.4. Substitution of Expressions

  A number of functions are provided for performing substitutions within a
tree. All take a tree and a description of old subexpressions to be replaced by
new ones. They come in non-destructive and destructive varieties and specify
substitution either by two arguments or by an association list.

The naming conventions for these functions and for their keyword arguments
generally follow the conventions for the generic sequence functions. See
chapter 14.

[Function]
subst new old tree &key :test :test-not :key
subst-if new test tree &key :key
subst-if-not new test tree &key :key

(subst new old tree) makes a copy of tree, substituting new for every subtree
or leaf of tree (whether the subtree or leaf is a car or a cdr of its parent)
such that old and the subtree or leaf satisfy the test. It returns the modified
copy of tree. The original tree is unchanged, but the result tree may share
with parts of the argument tree.

-------------------------------------------------------------------------------
Compatibility note: In MacLisp, subst is guaranteed not to share with the tree
argument, and the idiom (subst nil nil x) was used to copy a tree x. In Common
Lisp, the function copy-tree should be used to copy a tree, as the subst idiom
will not work.
-------------------------------------------------------------------------------

For example:

(subst 'tempest 'hurricane
       '(shakespeare wrote (the hurricane)))
   => (shakespeare wrote (the tempest))

(subst 'foo 'nil '(shakespeare wrote (twelfth night)))
   => (shakespeare wrote (twelfth night . foo) . foo)

(subst '(a . cons) '(old . pair)
       '((old . spice) ((old . shoes) old . pair) (old . pair))
       :test #'equal)
   => ((old . spice) ((old . shoes) a . cons) (a . cons))

This function is not destructive; that is, it does not change the car or cdr of
any already existing list structure. One possible definition of subst:

(defun subst (old new tree &rest x &key test test-not key)
  (cond ((satisfies-the-test old tree :test test
                             :test-not test-not :key key)
         new)
        ((atom tree) tree)
        (t (let ((a (apply #'subst old new (car tree) x))
                 (d (apply #'subst old new (cdr tree) x)))
             (if (and (eql a (car tree))
                      (eql d (cdr tree)))
                 tree
                 (cons a d))))))

See also substitute, which substitutes for top-level elements of a sequence.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Function]
nsubst new old tree &key :test :test-not :key
nsubst-if new test tree &key :key
nsubst-if-not new test tree &key :key

nsubst is a destructive version of subst. The list structure of tree is altered
by destructively replacing with new each leaf or subtree of the tree such that
old and the leaf or subtree satisfy the test.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Function]
sublis alist tree &key :test :test-not :key

sublis makes substitutions for objects in a tree (a structure of conses). The
first argument to sublis is an association list. The second argument is the
tree in which substitutions are to be made, as for subst. sublis looks at all
subtrees and leaves of the tree; if a subtree or leaf appears as a key in the
association list (that is, the key and the subtree or leaf satisfy the test),
it is replaced by the object with which it is associated. This operation is
non-destructive. In effect, sublis can perform several subst operations
simultaneously. For example:

(sublis '((x . 100) (z . zprime))
        '(plus x (minus g z x p) 4 . x))
   => (plus 100 (minus g zprime 100 p) 4 . 100)

(sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y)))
        '(* (/ (+ x y) (+ x p)) (- x y))
        :test #'equal)
   => (* (/ (- x y) (+ x p)) (+ x y))

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Function]
nsublis alist tree &key :test :test-not :key

nsublis is like sublis but destructively modifies the relevant parts of the
tree.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------

15.5. Using Lists as Sets

Common Lisp includes functions that allow a list of items to be treated as a
set. There are functions to add, remove, and search for items in a list, based
on various criteria. There are also set union, intersection, and difference
functions.

The naming conventions for these functions and for their keyword arguments
generally follow the conventions that apply to the generic sequence functions.
See chapter 14.

[Function]
member item list &key :test :test-not :key
member-if predicate list &key :key
member-if-not predicate list &key :key

The list is searched for an element that satisfies the test. If none is found,
nil is returned; otherwise, the tail of list beginning with the first element
that satisfied the test is returned. The list is searched on the top level
only. These functions are suitable for use as predicates.

For example:

(member 'snerd '(a b c d)) => nil
(member-if #'numberp '(a #¥Space 5/3 foo)) => (5/3 foo)
(member 'a '(g (a y) c a d e a f)) => (a d e a f)

Note, in the last example, that the value returned by member is eq to the
portion of the list beginning with a. Thus rplaca on the result of member may
be used to alter the found list element, if a check is first made that member
did not return nil.

See also find and position.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------
Compatibility note: In MacLisp, the member function uses an equal comparison
rather than eql, which is the default test for member in Common Lisp. Where in
MacLisp one would write (member x y), in Common Lisp one must write (member x y
:test #'equal) to get a completely identical effect. Similarly, one can get the
precise effect, and no more, of the MacLisp (memq x y) by writing in Common
Lisp (member x y :test #'eq).
-------------------------------------------------------------------------------

[Function]
tailp sublist list

This predicate is true if sublist is a sublist of list (that is, one of the
conses that makes up list); otherwise it is false. Another way to look at this
is that tailp is true if (nthcdr n list) is sublist, for some value of n. See
ldiff.

[change_begin]
X3J13 voted in January 1989 (TAILP-NIL)   to strike the parenthetical remark
that suggests that the sublist must be a cons, to clarify that tailp is true if
and only if there exists an integer n such that

(eql sublist (nthcdr n list))

and to specify that list may be a dotted list (implying that implementations
must use atom and not endp to check for the end of the list).
[change_end]

[Function]
adjoin item list &key :test :test-not :key

adjoin is used to add an element to a set, provided that it is not already a
member. The equality test defaults to eql.

(adjoin item list) == (if (member item list) list (cons item list))

In general, the test may be any predicate; the item is added to the list only
if there is no element of the list that ``satisfies the test.''

adjoin deviates from the usual rules described in chapter 14 for the treatment
of arguments named item and :key. If a :key function is specified, it is
applied to item as well as to each element of the list. The rationale is that
if the item is not yet in the list, it soon will be, and so the test is more
properly viewed as being between two elements rather than between a separate
item and an element.

(adjoin item list :key fn)
  == (if (member (funcall fn item) list

See pushnew.

[change_begin]
Notice of correction. In the first edition, the form (fn item) appeared in this
example without the required funcall.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Function]
union list1 list2 &key :test :test-not :key
nunion list1 list2 &key :test :test-not :key

union takes two lists and returns a new list containing everything that is an
element of either of the lists. If there is a duplication between two lists,
only one of the duplicate instances will be in the result. If either of the
arguments has duplicate entries within it, the redundant entries may or may not
appear in the result. For example:

(union '(a b c) '(f a d))
   => (a b c f d) or (b c f a d) or (d f a b c) or ...

(union '((x 5) (y 6)) '((z 2) (x 4)) :key #'car)
   => ((x 5) (y 6) (z 2)) or ((x 4) (y 6) (z 2)) or ...

There is no guarantee that the order of elements in the result will reflect the
ordering of the arguments in any particular way. The implementation is
therefore free to use any of a variety of strategies. The result list may share
cells with, or be eq to, either of the arguments if appropriate.

In general, the test may be any predicate, and the union operation may be
described as follows. For all possible ordered pairs consisting of one element
from list1 and one element from list2, the test is used to determine whether
they ``match.'' For every matching pair, at least one of the two elements of
the pair will be in the result. Moreover, any element from either list that
matches no element of the other will appear in the result. All this is very
general, but probably not particularly useful unless the test is an equivalence
relation.

The :test-not argument can be useful when the test function is the logical
negation of an equivalence test. A good example of this is the function
mismatch, which is logically inverted so that possibly useful information can
be returned if the arguments do not match. This additional ``useful
information'' is discarded in the following example; mismatch is used purely as
a predicate.

(union '(#(a b) #(5 0 6) #(f 3))
       '(#(5 0 6) (a b) #(g h))
       :test-not
       #'mismatch)
   => (#(a b) #(5 0 6) #(f 3) #(g h))     ;One possible result
   => ((a b) #(f 3) #(5 0 6) #(g h))      ;Another possible result

Using :test-not #'mismatch differs from using :test #'equalp, for example,
because mismatch will determine that #(a b) and (a b) are the same, while
equalp would regard them as not the same.

nunion is the destructive version of union. It performs the same operation but
may destroy the argument lists, perhaps in order to use their cells to
construct the result.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
permissible side effects of certain operations; nunion is permitted to perform
a setf on any part, car or cdr, of the top-level list structure of any of the
argument lists.
[change_end]

[Function]
intersection list1 list2 &key :test :test-not :key
nintersection list1 list2 &key :test :test-not :key

intersection takes two lists and returns a new list containing everything that
is an element of both argument lists. If either list has duplicate entries, the
redundant entries may or may not appear in the result. For example:

(intersection '(a b c) '(f a d)) => (a)

There is no guarantee that the order of elements in the result will reflect the
ordering of the arguments in any particular way. The implementation is
therefore free to use any of a variety of strategies. The result list may share
cells with, or be eq to, either of the arguments if appropriate.

In general, the test may be any predicate, and the intersection operation may
be described as follows. For all possible ordered pairs consisting of one
element from list1 and one element from list2, the test is used to determine
whether they ``match.'' For every matching pair, exactly one of the two
elements of the pair will be put in the result. No element from either list
appears in the result that does not match an element from the other list. All
this is very general, but probably not particularly useful unless the test is
an equivalence relation.

nintersection is the destructive version of intersection. It performs the same
operation, but may destroy list1, perhaps in order to use its cells to
construct the result. (The argument list2 is not destroyed.)

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
permissible side effects of certain operations; nintersection is permitted to
perform a setf on any part, car or cdr, of the top-level list structure of any
of the argument lists.
[change_end]

[Function]
set-difference list1 list2 &key :test :test-not :key
nset-difference list1 list2 &key :test :test-not :key

set-difference returns a list of elements of list1 that do not appear in list2.
This operation is not destructive.

There is no guarantee that the order of elements in the result will reflect the
ordering of the arguments in any particular way. The implementation is
therefore free to use any of a variety of strategies. The result list may share
cells with, or be eq to, either of the arguments if appropriate.

In general, the test may be any predicate, and the set difference operation may
be described as follows. For all possible ordered pairs consisting of one
element from list1 and one element from list2, the test is used to determine
whether they ``match.'' An element of list1 appears in the result if and only
if it does not match any element of list2. This is very general and permits
interesting applications. For example, one can remove from a list of strings
all those strings containing one of a given list of characters:

;; Remove all flavor names that contain "c" or "w".
(set-difference '("strawberry" "chocolate" "banana"
                  "lemon" "pistachio" "rhubarb")
                '(#¥c #¥w)
                :test
                #'(lambda (s c) (find c s)))
   => ("banana" "rhubarb" "lemon")     ;One possible ordering

nset-difference is the destructive version of set-difference. This operation
may destroy list1.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------
Compatibility note: An approximately equivalent Interlisp function is
ldifference.
-------------------------------------------------------------------------------

[Function]

set-exclusive-or list1 list2 &key :test :test-not :key
nset-exclusive-or list1 list2 &key :test :test-not :key

set-exclusive-or returns a list of elements that appear in exactly one of list1
and list2. This operation is not destructive.

There is no guarantee that the order of elements in the result will reflect the
ordering of the arguments in any particular way. The implementation is
therefore free to use any of a variety of strategies. The result list may share
cells with, or be eq to, either of the arguments if appropriate.

In general, the test may be any predicate, and the set-exclusive-or operation
may be described as follows. For all possible ordered pairs consisting of one
element from list1 and one element from list2, the test is used to determine
whether they ``match.'' The result contains precisely those elements of list1
and list2 that appear in no matching pair.

nset-exclusive-or is the destructive version of set-exclusive-or. Both lists
may be destroyed in producing the result.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
permissible side effects of certain operations; nset-exclusive-or is permitted
to perform a setf on any part, car or cdr, of the top-level list structure of
any of the argument lists.
[change_end]

[Function]
subsetp list1 list2 &key :test :test-not :key

subsetp is a predicate that is true if every element of list1 appears in
(``matches'' some element of) list2, and false otherwise.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------

15.6. Association Lists

An association list, or a-list, is a data structure used very frequently in
Lisp. An a-list is a list of pairs (conses); each pair is an association. The
car of a pair is called the key, and the cdr is called the datum.

An advantage of the a-list representation is that an a-list can be
incrementally augmented simply by adding new entries to the front. Moreover,
because the searching function assoc searches the a-list in order, new entries
can ``shadow'' old entries. If an a-list is viewed as a mapping from keys to
data, then the mapping can be not only augmented but also altered in a
non-destructive manner by adding new entries to the front of the a-list.

Sometimes an a-list represents a bijective mapping, and it is desirable to
retrieve a key given a datum. For this purpose, the ``reverse'' searching
function rassoc is provided. Other variants of a-list searches can be
constructed using the function find or member.

It is permissible to let nil be an element of an a-list in place of a pair.
Such an element is not considered to be a pair but is simply passed over when
the a-list is searched by assoc.

[Function]
acons key datum a-list

acons constructs a new association list by adding the pair (key . datum) to the
old a-list.

(acons x y a) == (cons (cons x y) a)

[change_begin]
This is a trivial convenience function, but I find I use it a lot.
[change_end]

[Function]
pairlis keys data &optional a-list

pairlis takes two lists and makes an association list that associates elements
of the first list to corresponding elements of the second list. It is an error
if the two lists keys and data are not of the same length. If the optional
argument a-list is provided, then the new pairs are added to the front of it.

The new pairs may appear in the resulting a-list in any order; in particular,
either forward or backward order is permitted. Therefore the result of the call

(pairlis '(one two) '(1 2) '((three . 3) (four . 19)))

might be

((one . 1) (two . 2) (three . 3) (four . 19))

but could equally well be

((two . 2) (one . 1) (three . 3) (four . 19))

[Function]
assoc item a-list &key :test :test-not :key
assoc-if predicate a-list
assoc-if-not predicate a-list

[change_begin]
X3J13 voted in March 1988 (ASSOC-RASSOC-IF-KEY)   to allow assoc-if and
assoc-if-not also to take a keyword argument named :key, to be used to
determine whether a pair ``satisfies the test'' in the same manner as for
sequence functions. The new function descriptions are therefore as follows:

[Function]
assoc-if predicate a-list &key :key
assoc-if-not predicate a-list &key :key

The omission of :key arguments for these functions in the first edition was
probably an oversight.
[change_end]

Each of these searches the association list a-list. The value is the first pair
in the a-list such that the car of the pair satisfies the test, or nil if there
is no such pair in the a-list. For example:

(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
        =>  (r . x)
(assoc 'goo '((foo . bar) (zoo . goo))) => nil
(assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) => (2 b c d)

It is possible to rplacd the result of assoc provided that it is not nil, in
order to ``update'' the ``table'' that was assoc's second argument. (However,
it is often better to update an a-list by adding new pairs to the front, rather
than altering old pairs.) For example:

(setq values '((x . 100) (y . 200) (z . 50)))
(assoc 'y values) => (y . 200)
(rplacd (assoc 'y values) 201)
(assoc 'y values) => (y . 201) now

A typical trick is to say (cdr (assoc x y)). Because the cdr of nil is
guaranteed to be nil, this yields nil if no pair is found or if a pair is found
whose cdr is nil. This is useful if nil serves its usual role as a ``default
value.''

The two expressions

(assoc item list :test fn)

and

(find item list :test fn :key #'car)

are equivalent in meaning with one important exception: if nil appears in the
a-list in place of a pair, and the item being searched for is nil, find will
blithely compute the car of the nil in the a-list, find that it is equal to the
item, and return nil, whereas assoc will ignore the nil in the a-list and
continue to search for an actual pair (cons) whose car is nil. See find and
position.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------
Compatibility note: In MacLisp, the assoc function uses an equal comparison
rather than eql, which is the default test for assoc in Common Lisp. Where in
MacLisp one would write (assoc x y), in Common Lisp one must write (assoc x y
:test #'equal) to get the completely identical effect. Similarly, one can get
the precise effect, and no more, of the MacLisp (assq x y) by writing in Common
Lisp (assoc x y :test #'eq).
-------------------------------------------------------------------------------

In Interlisp, assoc uses an eq test, and sassoc uses an Interlisp equal test.

[Function]
rassoc item a-list &key :test :test-not :key
rassoc-if predicate a-list
rassoc-if-not predicate a-list

[change_begin]
X3J13 voted in March 1988 (ASSOC-RASSOC-IF-KEY)   to allow rassoc-if and
rassoc-if-not also to take a keyword argument named :key, to be used to
determine whether a pair ``satisfies the test'' in the same manner as for
sequence functions. The new function descriptions are therefore as follows:

[Function]
rassoc-if predicate a-list &key :key
rassoc-if-not predicate a-list &key :key

The omission of :key arguments for these functions in the first edition was
probably an oversight.
[change_end]

rassoc is the reverse form of assoc; it searches for a pair whose cdr satisfies
the test, rather than the car. If the a-list is considered to be a mapping,
then rassoc treats the a-list as representing the inverse mapping. For example:

(rassoc 'a '((a . b) (b . c) (c . a) (z . a))) => (c . a)

The expressions

(rassoc item list :test fn)

and

(find item list :test fn :key #'cdr)

are equivalent in meaning, except when the item is nil and nil appears in place
of a pair in the a-list. See the discussion of the function assoc.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

-------------------------------------------------------------------------------